/*
---------- Library map ----------
pointInRect
collide_Rect_Rect_S
rectToRect			NO
	rayToRect
rayToHorLine		NO
rayToVertLine		NO
rayToCircle			NO
circleVToRect		NO
	rayToVertLine
	rayToHorLine
rayToRect			NO
	rayToVertLine
	rayToHorLine
rayToSegment		NO	- largest function
rectToSegment		NO
	rayToSegment
	rayToHorLine
	rayToVertLine

intersectSegments
	linesIntersect
linesIntersect
*linesIntersectFast

collection of simple intersection and overlaping tests
all the functions but linesIntersect() return bool indicating that test is positive
tests are performed on the following primitives:
	point2
	rect
	circle
	line segment
*/

#include <assert.h>
#include "physics.h"

#include "tools.h"
#include "point2.h"
#include "rect.h"
//#include "polygon.h"
#include "circle.h"
#include "globals.h"

#define _OPTIMIZE_rectToRect
#define _OPTIMIZE_circleVToRect
#define _OPTIMIZE_rayToRect
#define _OPTIMIZE_rectToSegment

//unsigned int g_ctr1=0, g_ctr2=0, g_ctr3=0;	//? for debug

Physics* Physics::_instance = 0;

Physics::Physics(){
};

Physics* Physics::Instance(){

	if (_instance == 0){
	
		_instance = new Physics;
	}
	return _instance;
}

//#define SAME_SIGNS( a, b )	\
//		(((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
bool SAME_SIGNS(float a, float b){

	return (a<0 && b<0) || (a>=0 && b>=0);
}

// check if a point (x,y) is in rectangle rect
bool Physics::pointInRect(float x, float y, Rect* rect){

	assert(rect);

	if(x<rect->xLo)	return false;
	if(x>rect->xHi)	return false;
	if(y<rect->yLo)	return false;

	// optimisation: one line instead of 2	//?
//	if(y>rect->yHi)	return false;
//	return true;
	return y<=rect->yHi;
}

// check if rectangles r1 and r2 are overlapping
// if some edges overlap (like if they are equal) - returns true
//? optimisation: on modern processors it could be faster to write it all in one line (not using ifs)
bool Physics::collide_Rect_Rect_S(Rect* r1, Rect* r2){

	assert(r1);
	assert(r2);

	if(r1->yHi < r2->yLo)
		return false;
	if(r1->yLo > r2->yHi)
		return false;
	if(r1->xHi < r2->xLo)
		return false;

	// optimisation: one line instead of 2
//	if(r1->xLo > r2->xHi)
//		return false;
//	return true;
	return r1->xLo <= r2->xHi;
}

// check if rectangle 'd' moving by vector 'v' intersects with rectangle 's'
// return 't_min' of 'v'
//? it is posiible to optimize here and not in collideToPlatforms - here is better
bool Physics::rectToRect(Rect* s, Rect* d, Point2* v, Point2* n, float* t_min){

	Point2 o, normal;
	float t_tmp;
	bool res =false;

/*
   xLo,yHi--------xHi,yHi
          |      |
		  |      |
		  |      |
   xLo,yLo--------xHi,yLo
*/
	// a ray is projected for all the 4 points of the moving rect
	o.x =d->xLo;
	o.y =d->yLo;
	#ifdef _OPTIMIZE_rectToRect
	if( (v->x<0 && o.x>=s->xHi) || (v->y<0 && o.y >=s->yHi) )	//{O}
	#endif
	if(rayToRect(s, &o, v, &t_tmp, &normal)){

//		if(t_tmp<*t_min){	// first time
			*t_min =t_tmp;
			*n =normal;
			res =true;
//		}
	}

	o.x =d->xLo;
	o.y =d->yHi;
	#ifdef _OPTIMIZE_rectToRect
	if( (v->x<0 && o.x>=s->xHi) || (v->y>0 && o.y <=s->yLo) )	//{O}
	#endif
	if(rayToRect(s, &o, v, &t_tmp, &normal)){

		if(!res || t_tmp<*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	o.x =d->xHi;
	o.y =d->yHi;
	#ifdef _OPTIMIZE_rectToRect
	if( (v->x>0 && o.x<=s->xLo) || (v->y>0 && o.y <=s->yLo) )	//{O}
	#endif
	if(rayToRect(s, &o, v, &t_tmp, &normal)){

		if(!res || t_tmp<*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	o.x =d->xHi;
	o.y =d->yLo;
	#ifdef _OPTIMIZE_rectToRect
	if( (v->x>0 && o.x<=s->xLo) || (v->y<0 && o.y>=s->yHi) )	//{O}
	#endif
	if(rayToRect(s, &o, v, &t_tmp, &normal)){

		if(!res || t_tmp<*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	return res;
}

float TTT = 1000;
//----------------------- ray tests -----------------
// ray to horisontal line test
// line at level 'lineY'
//? x can be used instead of using *t 4 times
bool Physics::rayToHorLine(float lineY, float lineXlo, float lineXhi, Point2* rayO, Point2* rayD, float* t){

	float x;

	#ifndef _OPTIMIZE_rayToRect
	if(rayD->y==0)
		return false;
	#endif

	*t =(lineY-rayO->y)/rayD->y;

	// if the ray intersects the line
	if(*t<0 || *t>1){
		return false;
	}

	x =rayO->x +*t*rayD->x;
	// if the ray intersects the line at the segment return true
	return (x>lineXlo && x<lineXhi);
}

// ray to vertical line test
// line at x 'lineX'
bool Physics::rayToVertLine(float lineX, float lineYlo, float lineYhi, Point2* rayO, Point2* rayD, float* t){

	float y;

	#ifndef _OPTIMIZE_rayToRect
	if(rayD->x==0)
		return false;
	#endif

	*t =(lineX-rayO->x)/rayD->x;
	// if the ray intersects the line
	if(*t<0 || *t>1){
		return false;
	}

	y =rayO->y +*t*rayD->y;
	// if the ray intersects the line at the segment return true
	return (y>lineYlo && y<lineYhi);
}

// check if circle at 'origin' with radius 'radius' is intersected by ray 'V' from 'o'
// return 't_min' of 'V'
bool Physics::rayToCircle(Point2* origin, float radius, Point2* o, Point2* V, float* t_min){

	float a,b,c,d,x1,x2,y1,y2,x3,y3,r,t_tmp;

	x1 =o->x;
	y1 =o->y;

	x2 =x1 +V->x;
	y2 =y1 +V->y;

	x3 =origin->x;
	y3 =origin->y;

	r =radius;

	// solve quadratic equation
	a = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1);
	b = 2*( (x2 - x1)*(x1 - x3) + (y2 - y1)*(y1 - y3) );
	c =	x3*x3 + y3*y3 + x1*x1 + y1*y1 - 2*(x3*x1 + y3*y1) - r*r;	
	d =b*b -4*a*c;

	// there is no solution
	if(d<=0) 
		return false;

	if(d>0){

		*t_min =(-b +(float)sqrt(d))/(2.0f*a);
		t_tmp =(-b -(float)sqrt(d))/(2.0f*a);
		// only one solution interests us

		if(t_tmp>0 && t_tmp<1){

			if(*t_min>0 && *t_min<1){

				if(t_tmp<*t_min){

					*t_min =t_tmp;
				}
			}
			else{

				*t_min =t_tmp;
			}

			return true;
		}
		else if(*t_min>0 && *t_min<1){
		
			return true;
		}
	}

	return false;
}

// check if moving (by 'V') circle 'circle' intersects with rectangle 'rect'
// return 't_min' of 'V' and normal to the rectangle in intersection point
bool Physics::circleVToRect(float radius, Point2* origin, Rect* rect, Point2* V, Point2* n, float* t_min){

	float t_tmp;
	bool res =false;	

	// we do it by moving the rect closer by radius to the circle and throwing rays from the circle's origin
	// no need to check if(t_tmp>0 && t_tmp<=1) as we already did it in other ray routines
	#ifdef _OPTIMIZE_circleVToRect
	if(V->x>0)
	#endif
	// check it against vertical low
	if(rayToVertLine(rect->xLo -radius, rect->yLo, rect->yHi, origin, V, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
//			if(!res || (res && t_tmp<*t_min)){	// first time
				*t_min =t_tmp;
				n->x =-1;
				n->y =0;
				res =true;
//			}
//		}
	}

	#ifdef _OPTIMIZE_circleVToRect
	if(V->x<0)
	#endif
	// check it against vertical hi
	if(rayToVertLine(rect->xHi +radius, rect->yLo, rect->yHi, origin, V, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){
				*t_min =t_tmp;
				n->x =1;
				n->y =0;
				res =true;
			}
//		}
	}

	#ifdef _OPTIMIZE_circleVToRect
	if(V->y>0)
	#endif
	// check it against horisontal low
	if(rayToHorLine(rect->yLo -radius, rect->xLo, rect->xHi, origin, V, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){
				*t_min =t_tmp;
				n->x =0;
				n->y =-1;
				res =true;
			}
//		}
	}

	#ifdef _OPTIMIZE_circleVToRect
	if(V->y<0)
	#endif
	// check it against horisontal hi
	if(rayToHorLine(rect->yHi +radius, rect->xLo, rect->xHi, origin, V, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){
				*t_min =t_tmp;
				n->x =0;
				n->y =1;
				res =true;
			}
//		}
	}

	return res;
}

// check if ray intersect rectangle 'rect'
// return 't_min' and normal to the rectangle in intersection point
bool Physics::rayToRect(Rect* rect, Point2* o, Point2* d, float* t_min, Point2* normal){

	float t_tmp;
	bool res =false;

	#ifdef _OPTIMIZE_rayToRect
	if(d->x>0)
	#endif
	if(rayToVertLine(rect->xLo, rect->yLo, rect->yHi, o, d, &t_tmp)){

    	// no need to check if(t_tmp>0 && t_tmp<=1) as we already did it in other ray routines
//		if(t_tmp>0 && t_tmp<=1){	// first time
//			if(!res || (res && (t_tmp<*t_min))){
				*t_min =t_tmp;
				normal->x =-1;
				normal->y =0;
				res =true;
//			}
//		}
	}

	#ifdef _OPTIMIZE_rayToRect
	if(d->y<0)
	#endif
	if(rayToHorLine(rect->yHi, rect->xLo, rect->xHi, o, d, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){
				*t_min =t_tmp;
				normal->x =0;
				normal->y =1;
				res =true;
			}
//		}
	}

	#ifdef _OPTIMIZE_rayToRect
	if(d->x<0)
	#endif
	if(rayToVertLine(rect->xHi, rect->yLo, rect->yHi, o, d, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){

				*t_min =t_tmp;
				normal->x =1;
				normal->y =0;
				res =true;
			}
//		}
	}

	#ifdef _OPTIMIZE_rayToRect
	if(d->y>0)
	#endif
	if(rayToHorLine(rect->yLo, rect->xLo, rect->xHi, o, d, &t_tmp)){

//		if(t_tmp>0 && t_tmp<=1){
			if(!res || t_tmp<*t_min){
				*t_min =t_tmp;
				normal->x =0;
				normal->y =-1;
				res =true;
			}
//		}
	}

	return res;
}

// check if ray intersects segment 's1-s2'
// return 't_min' and normal to the segment in intersection point
//? should be optimized -> operator
bool Physics::rayToSegment(Point2* s1, Point2* s2, Point2* rayO, Point2* rayD, Point2* n, float* t){

	float k,b,tmp;
	Point2 p_tmp;
/*
	// we do these ckecks not for optimization, but in order not to delete by 0
	// if the segment is actually a vertical line
	if(s1->x == s2->x){

		assert(0 && "segment is vertical line");
		if(s1->y <s2->y)
			return rayToVertLine(s1->x, s1->y, s2->y,rayO, rayD, t);
		else
			return rayToVertLine(s1->x, s2->y, s1->y,rayO, rayD, t);
	}
	// if the segment is actually a horisontal line
	if(s1->y == s2->y){

		assert(0 && "segment is horisontal line");
		if(s1->x <s2->x)
			return rayToVertLine(s1->y, s1->x, s2->x,rayO, rayD, t);
		else
			return rayToVertLine(s1->y, s2->x, s1->x,rayO, rayD, t);
	}
*/
	// y =b +kx									// line equation
	k =(s1->y -s2->y)/(s1->x -s2->x);			// get inclination (tangens of the angle)
	b =s1->y -k*s1->x;							// find b

	tmp =rayD->y -k*rayD->x;					// tmp - is ray's b - it is 0. here we check if k satisfies this equation, then the ray is parallel to the line
	if(tmp==0){									// ray is parallel to the line
//		assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==PARALLEL);
		return false;							
	}

	*t =(k*rayO->x +b -rayO->y)/tmp;			// solve the parametric equation
	if(*t<0 || *t>1){							// if the ray doesnt intersect the line	//? >= or >
//		assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
		return false;
	}
		
	
	p_tmp =*rayD*(*t) +*rayO;					// check that the point of intersection if on the segment (inside segment's rectangle)
	if(s1->y >s2->y){

		if(p_tmp.y >s1->y){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
		if(p_tmp.y <s2->y){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
	}
	else{

		if(p_tmp.y <s1->y){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
		if(p_tmp.y >s2->y){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
	}

	if(s1->x >s2->x){

		if(p_tmp.x >s1->x){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
		if(p_tmp.x <s2->x){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
	}
	else{

		if(p_tmp.x <s1->x){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
		if(p_tmp.x >s2->x){
			assert(intersectSegments(s1, s2, rayO, &(*rayO+*rayD), &V_TMP) ==DONT_INTERSECT);
			return false;
		}
	}

	n->x =s2->y -s1->y;
	n->y =s1->x -s2->x;
	return true;
}

// given rectangle "rect", segment "s1 - s2", n - valid vector, t_min - valid float
// the function returns true is the 'rect' moving by 'v' collides with the segmet
// if so, 'n' set to the normal at the point of collision, and t_min - t min
//? optimise ->
bool Physics::rectToSegment(Rect* rect, Point2* s1, Point2* s2, Point2* v, Point2* n, float* t_min){

	Point2 dLoLo, dLoHi, dHiLo, dHiHi, normal, v_tmp;
	float t_tmp;
	bool res =false;

	// set 4 edgepoints of the rectangle
	dLoLo.x =rect->xLo;
	dLoLo.y =rect->yLo;
	dHiLo.x =rect->xHi;
	dHiLo.y =rect->yLo;

	dLoHi.x =rect->xLo;
	dLoHi.y =rect->yHi;
	dHiHi.x =rect->xHi;
	dHiHi.y =rect->yHi;

	// for all the 4 edges of the rectangle - check if them penetrate the slope
	#ifdef _OPTIMIZE_rectToSegment
	if(v->x<0 || v->y<0)
	#endif
	if(rayToSegment(s1, s2, &dLoLo, v, &normal, &t_tmp)){

//		if(!res || (res && t_tmp <*t_min) ){	// first time
			*t_min =t_tmp;
			*n =normal;
			res =true;
//		}
	}

	#ifdef _OPTIMIZE_rectToSegment
	if(v->x>0 || v->y<0)
	#endif
	if(rayToSegment(s1, s2, &dHiLo, v, &normal, &t_tmp)){

		if(!res || t_tmp <*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	#ifdef _OPTIMIZE_rectToSegment
	if(v->x<0 || v->y>0)
	#endif
	if(rayToSegment(s1, s2, &dLoHi, v, &normal, &t_tmp)){

		if(!res || t_tmp <*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	#ifdef _OPTIMIZE_rectToSegment
	if(v->x>0 || v->y>0)
	#endif
	if(rayToSegment(s1, s2, &dHiHi, v, &normal, &t_tmp)){

		if(!res || t_tmp <*t_min){

			*t_min =t_tmp;
			*n =normal;
			res =true;
		}
	}

	// it is stil possible that the slope penetrates the segment
	v_tmp =-*v;
	// for all the 4 sides of the rectangle

	// check hit against rectangle's bottom
	#ifdef _OPTIMIZE_rectToSegment
	if(v->y<0){
		if(s1->y>s2->y){
	#endif
			if(rayToHorLine(rect->yLo, rect->xLo, rect->xHi, s1, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->y =1;
					n->x =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
		}
		else
	#endif
			if(rayToHorLine(rect->yLo, rect->xLo, rect->xHi, s2, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->y =1;
					n->x =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
	}
	#endif

	// check hit against rectangle's top
	#ifdef _OPTIMIZE_rectToSegment
	if(v->y>0){
		if(s1->y<s2->y){
	#endif
			if(rayToHorLine(rect->yHi, rect->xLo, rect->xHi, s1, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->y =-1;
					n->x =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
		}
		else
	#endif
			if(rayToHorLine(rect->yLo, rect->xLo, rect->xHi, s2, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->y=-1;
					n->x =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
	}
	#endif

	// check hit against rectangle's right (xHi)
	#ifdef _OPTIMIZE_rectToSegment
	if(v->x>0){
		if(s1->x<s2->x){
	#endif
			if(rayToVertLine(rect->xHi, rect->yLo, rect->yHi, s1, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->x =-1;
					n->y =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
		}
		else
	#endif
			if(rayToVertLine(rect->xHi, rect->yLo, rect->yHi, s2, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->x =-1;
					n->y =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
	}
	#endif

	// check hit against rectangle's left (xLo)
	#ifdef _OPTIMIZE_rectToSegment
	if(v->x<0){
		if(s1->x>s2->x){
	#endif
			if(rayToVertLine(rect->xLo, rect->yLo, rect->yHi, s1, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->x =1;
					n->y =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
		}
		else
	#endif
			if(rayToVertLine(rect->xLo, rect->yLo, rect->yHi, s2, &v_tmp, &t_tmp)){

				if(!res || t_tmp <*t_min){

					*t_min =t_tmp;
					n->x =1;
					n->y =0;
					res =true;
				}
			}
	#ifdef _OPTIMIZE_rectToSegment
	}
	#endif

	return res;
}

// aux ---------------------------------------------------------------

// check if segments p1-p2 and p3-p4 intersect
// return point of ntersection 'ret'
bool Physics::intersectSegments(const Point2* p1, const Point2* p2, const Point2* p3, const Point2* p4, Point2* ret){

	assert(p1);
	assert(p2);
	assert(p3);
	assert(p4);

	return (DO_INTERSECT==linesIntersect(p1->x, p1->y, p2->x, p2->y, p3->x, p3->y, p4->x, p4->y, &(ret->x), &(ret->y)));
}

// used by intersectSegments()
int Physics::linesIntersect(float x1, float y1,   // First line segment 
		     float x2, float y2,

		     float x3, float y3,   // Second line segment 
		     float x4, float y4,

		     float* x,
		     float* y         // Output value:
		                // point of intersection
               )
{
    float a1, a2, b1, b2, c1, c2; // Coefficients of line eqns. 
    float r1, r2, r3, r4;         // 'Sign' values 
    float denom, num;     // Intermediate values 

    // Compute a1, b1, c1, where line joining points 1 and 2
     // is "a1 x  +  b1 y  +  c1  =  0".
     //

    a1 = y2 - y1;
    b1 = x1 - x2;
    c1 = x2 * y1 - x1 * y2;

    // Compute r3 and r4.


    r3 = a1 * x3 + b1 * y3 + c1;
    r4 = a1 * x4 + b1 * y4 + c1;

    // Check signs of r3 and r4.  If both point 3 and point 4 lie on
     // same side of line 1, the line segments do not intersect.
     //

    if ( r3 != 0 &&
         r4 != 0 &&
         SAME_SIGNS( r3, r4 ))
        return ( DONT_INTERSECT );

    // Compute a2, b2, c2 

    a2 = y4 - y3;
    b2 = x3 - x4;
    c2 = x4 * y3 - x3 * y4;

    // Compute r1 and r2 

    r1 = a2 * x1 + b2 * y1 + c2;
    r2 = a2 * x2 + b2 * y2 + c2;

    // Check signs of r1 and r2.  If both point 1 and point 2 lie
     // on same side of second line segment, the line segments do
     // not intersect.
     //

    if ( r1 != 0 &&
         r2 != 0 &&
         SAME_SIGNS( r1, r2 ))
        return ( DONT_INTERSECT );

    // Line segments intersect: compute intersection point. 

    denom = a1 * b2 - a2 * b1;
    if ( denom == 0 )
        return ( PARALLEL );
//    offset = denom < 0 ? - denom / 2 : denom / 2;

    // The denom/2 is to get rounding instead of truncating.  It
     // is added or subtracted to the numerator, depending upon the
     // sign of the numerator.
     //

    num = b1 * c2 - b2 * c1;
//    *x = ( num < 0 ? num - offset : num + offset ) / denom;
    *x = num / denom;

    num = a2 * c1 - a1 * c2;
    *y = num / denom;

    return ( DO_INTERSECT );
    } // lines_intersect 


//-------------------------------------------------------------------------------------------------
// Faster Line Segment Intersection
// Franklin Antonio
/*
int Physics::linesIntersectFast(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float* x, float* y) 
{

	float Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
	float x1lo,x1hi,y1lo,y1hi;

	Ax = x2-x1;
	Bx = x3-x4;

	// X bound box test
	if(Ax<0) {						
		x1lo=x2; 
		x1hi=x1;
	} 
	else {
		x1hi=x2; 
		x1lo=x1;
	}
	if(Bx>0) {
		if(x1hi < x4 || x3 < x1lo) return DONT_INTERSECT;
	} 
	else {
		if(x1hi < x3 || x4 < x1lo) return DONT_INTERSECT;
	}

	Ay = y2-y1;
	By = y3-y4;

	// Y bound box test
	if(Ay<0) {						
		y1lo=y2; 
		y1hi=y1;
	} 
	else {
		y1hi=y2; 
		y1lo=y1;
	}
	if(By>0) {
		if(y1hi < y4 || y3 < y1lo) return DONT_INTERSECT;
	} else {
		if(y1hi < y3 || y4 < y1lo) return DONT_INTERSECT;
	}


	Cx = x1-x3;
	Cy = y1-y3;
	d = By*Cx - Bx*Cy;					// alpha numerator
	f = Ay*Bx - Ax*By;					// both denominator
	if(f>0) {							// alpha tests
		if(d<0 || d>f) return DONT_INTERSECT;
	} 
	else {
		if(d>0 || d<f) return DONT_INTERSECT;
	}

	e = Ax*Cy - Ay*Cx;					// beta numerator
	if(f>0) {							// beta tests
	if(e<0 || e>f) return DONT_INTERSECT;
	} 
	else {
		if(e>0 || e<f) return DONT_INTERSECT;
	}

	// compute intersection coordinates

	if(f==0) return PARALLEL;
	num = d*Ax;									// numerator 
	offset = SAME_SIGNS(num,f) ? f/2.0f : -f/2.0f;	// round direction
	*x = x1 + (num+offset) / f;					// intersection x

	num = d*Ay;
	offset = SAME_SIGNS(num,f) ? f/2.0f : -f/2.0f;
	*y = y1 + (num+offset) / f;					// intersection y

	return DO_INTERSECT;
}
*/